1. Field of the Invention
The invention generally relates to the implementation of computer networks, and more particularly, to a method and apparatus for efficient utilization of memory and reduced memory waste in storing data blocks of network traffic.
2. Background Description
In networks that employ various network protocols such as, for example, the Internet Protocol (IP) stack family and Fibre Channel protocol, packets are sent and received of varying sizes to deliver a wide variety of contents and messaging information including, for example, data, video, voice, control information, etc. In order to process these packets at the receiving side, e.g., a network interface, various techniques are used to manage the incoming stream of varying sizes of packets.
Typical arrangements include employing some form of logic, either hardware centric or software centric, to receive and temporarily store the incoming packets in a memory area, e.g., a buffer pool or equivalent, until subsequent processing can access and retrieve the packets, as appropriate, for action on the packet contents. These arrangements may also employ distributed processing or centralized processing.
This interaction between a network interface logic and subsequent processing often employs various types of buffering arrangements to manage the sequencing of the packets in the buffer pools so that arrival sequences are maintained in time ordered, or otherwise, sequence ordered relationship to one another. Often packets will contain sequencing information so that re-arrangement can occur to place information in proper order as necessary.
Additionally, observation and analysis of network traffic in various applications shows that transmitted packets typically fall within ranges of relative sizes, (e.g., small packets or big packets, etc. ). For example, for the Fibre Channel protocol, packets can range between a minimal packet size of 36 bytes to 2112 bytes. However, 50% of all packets exchanged are smaller than 100 bytes, whereas substantially the other half of packets are in the range of 1500 bytes and larger. Other protocols tend to exhibit similar statistical groupings of packet sizes and may have more groups or different ratios.
Typically. in network handlers interfaces, when packets arrive from the network at an input port, the hardware attached to the port usually communicates this information to a processor which performs routing actions and then passes the processed packet to an output port for delivery to its intended destination. The hardware attached to the input port is often a simple DMA circuit that receives the packet, writes it to memory, and then indicates to the controlling processor that a packet has been received.
The DMA controller is typically set up by using several registers which are written by the host processor. One of these registers contains the address of the memory area where the next packet received from the network is going to be stored. As the size of the packet is not known in advance, the assigned memory area is typically sized to fit the biggest packet allowed by the particular network protocol to avoid loss of data. As a result, memory is used inefficiently, as big chunks of memory area are assigned for storing small packets.
An alternative approach uses multiple linked smaller buffers for storing a received packet. If the received packet does not fit in a single small buffer, then several of those smaller buffers are linked together as a linked list to store a single packet. This results in better memory utilization, however, this introduces significant complexity in handling the packets.
Yet another approach uses dynamical allocation of memory for each packet. This requires lengthy searches to locate the sufficient available consequent memory block to fit the received packet, using one of the space allocating algorithms such as “first fit” or “best fit”. Drawbacks of this approach are that the search and allocation of the memory is slow, requiring the memory to be accessed and analyzed before an allocation can be made, as well as need for storing allocation information.